\chapter{信号量}
\thispagestyle{empty}

众所周知，要解决很多并发性问题都需要用到锁和条件变量。多年以前，最早实现这个的人之一是Edsger Dijkstra(尽管很难知道确切的历史[GR92])，关于他还有图论里著名的『最短路径』算法[D59]。关于结构化编程，早期有一个关于『goto语句有害』[D68a]的激烈辩论，在这里，我们将会介绍一个叫做信号量的同步原语[D68b,D72]。确实，Dijkstra以及他的同事为同步相关的所有问题的发明了唯一的原语信号量；正如你将看到的，既可以将信号量用作锁也可以用作条件变量。

Crux：如何使用信号量
我们如何使用信号量而不是锁和条件变量呢？信号量的定义是什么？binary信号量是什么？可以不用锁和条件变量很直接的构造信号量么？那么不用信号量来构造锁和条件变量呢？

\section{信号量定义}
信号量是包含一个整型值的对象，可以通过两个函数来操作它；在POSIX标准中，这两个函数是sem\_wait()和sem\_post()【脚标1】。因为信号量的初始值决定了它的行为，因此在调用其他函数与信号量交互之前，我们需要先给它初始化一个值，如图31.1代码所示：
\begin{verbatim}
#include <semaphore.h>
sem_t s;
sem_init(&s, 0, 1);
图31.1 初始化信号量
\end{verbatim}

图中，我们声明了一个信号量，并通过第三个参数传递1给它来将其初始化。sem\_init()第二个参数将会在所有的示例中设为0；这表明这个信号量是在同一个进程中的线程间共享的。欲知关于信号量在不同进程间来同步访问的，详见手册页，第二参数就需要设为另一个不同值。

信号量初始化之后，我们可以调用两个函数中的一个来操作该信号量。这两个函数的行为见图31.2。

代码图31.2\\

现在，我们不关心这两个函数的实现，这两个函数需要考虑一些问题；在多线程间调用sem\_wait()和sem\_post()，很明显需要管理这些临界区。我们将会关注如何使用这些原语；稍后我们再讨论如何构造它们。

我们应该讨论关于接口的几个主要方面。首先，我们可以发现sem\_wait()可能会立即返回（因为在调用sem\_wait()时信号量的值是1或者更大），也可能使得调用者暂停执行等待随后的post。当然，多个调用线程可能调用sem\_wait()，因此都排队等待被唤醒。

第二，我们可以发现sem\_post()并不像sem\_wait()一样等待某些特定的条件。而是，它只是简单的增加信号量的值，如果有线程正在等待被唤醒，就唤醒其中一个。

第三，当信号量的值是负值时，表示正在等待的线程数[D68b]。尽管信号量的值通常是对用户不可见的，这个值得了解一下，可能会帮助你记住信号量是如何运转的。

不要担心信号量之间表面上可能发生的竞争条件；假设他们的行为都是以原子方式执行的。很快我们会使用锁和条件变量来实现它。


\section{二进制信号量}
现在我们已经可以使用信号量了。我们即将见到的是我们已经很熟悉的：使用信号量用作锁。见图31.3的代码；其中，你们可以看到我们简单地在临界区周围添加了成对的sem\_wait()和sem\_post()。要使之能够有效的关键是信号量m的初始值（图中初始化为X）。X应当是多少呢？

代码图31.3\\

继续阅读之前，尝试考虑一下

回头看一下上面sem\_wait()和sem\_post()函数的定义，我们可以发现初始值应当为1。

为了使之更清楚，我们设想一个有两个线程的场景。第一个线程（线程0）调用sem\_wait()；它会首先将信号量的值减1，变为0。然后，只要信号量的值小于等于0，它就会等待；因为信号量的值为0，调用线程会之间返回并继续；线程0会自由的进入临界区。当线程0在临界区调用sem\_post()时，如果没有其他线程要获取这个锁，他就简单的将信号量的值设为1（不用唤醒其他等待线程，因为没有）。表31.1展示了这个场景的流程。

流程表31.1\\

当线程0持有这个锁但还未调用sem\_post()时，会有另一个更有意思的场景发生，另一个线程（线程1）试图通过调用sem\_wait()进入临界区。此时，线程1会将信号量的值减一，变为-1，因此会等待（使自己休眠并放弃处理器）。当线程0再次运行时，它会接着调用sem\_post()，使信号量的值加1，变为0，并唤醒等待线程（线程1），然后线程1会自己获取锁。当线程1结束时，她回再次将信号量的值加1，再次变为1。

流程表31.2\\

表31.2展示了这个例子的流程。除了线程的行为，这张表还列出了每个线程的调度状态：运行，就绪(可运行但未运行)，休眠。特别注意，线程1在试图获取已经被占用的锁时进入了休眠状态；只有当线程0在此运行时才能唤醒线程1并有可能继续在此运行。

如果你想要运行自己的例子，试试这个场景，多个线程排队等待同一个锁。信号量的值在这样的一个执行轨迹中会是什么呢？

因此，我们可以使用信号量作为锁。因为锁仅仅有两个状态（锁住，未锁住），这个用法有时候被称作二元信号量，实际上，这个可以以一个比这示例更简单的方式实现；我们使用通用的信号量作为锁。


\section{以信号量作为条件变量}
当线程想要在等待条件为真时停止执行时，信号量也很有用。比如，一个线程希望等待某个列表变为非空，那么它可以从中删除一个元素。在这个使用模式中，我们经常发现某个线程等待某些事情的发生，另一个线程促使这件事情发生且通知它事情的发生，因此唤醒等待线程。因为等待线程正在等待某些条件的改变，我们使用信号量作为条件变量。


代码图31.4\\

下面是一个简单的例子。设想某个线程创建了另一个线程，接着希望等待该线程结束（图31.4）。当这个程序运行时，我们会看到如下输出：
\begin{verbatim}
parent: begin
child
parent: end
\end{verbatim}


那么，问题是如何用信号量来达到这个效果呢？实际上，结果还是比较好理解的。正如代码中所示，parent简单地调用sem\_wait()，child调用sem\_post()来等待child结束执行的条件变为真。然而，问题是：信号量的初始值应该设为多少呢？

先不往下继续读，再考虑一下！

显而易见，信号量的初值应当设为0。需要考虑两种情况。首先，我们假设parent创建了child但是child还未运行（比如，child进入了就绪队列但未运行）。这种情况，见表31.3，parent会在child调用sem\_post()之前调用sem\_wait()；我们需要parent等待child运行。这种情况只可能在信号量的值不大于0时发生；因此，0是初始值。parent运行，信号量值减一，然后等待（休眠）。当child最终运行时，调用sem\_post()，信号量值加一至0，并唤醒parent，然后parent从sem\_wait()返回并结束程序。

表31.3\\

第二种情况（表31.4），当child在parent得到机会调用sem\_wait()之前结束运行。这中情况，child会先调用sem\_post()，因此信号量的值由0加1至1。当parent接着得到机会运行时，会调用sem\_wait()，发现信号量的值为1；parent因此将信号量减一至0，并直接从sem\_wait()返回，而不用等待，也达到了预期的效果。

表31.4\\


\section{生产者/消费者问题（有界缓冲区）}
本节我们将要面对的问题是著名的生产者/消费者问题，有时也叫做有界缓冲区问题[D72]。这个问题在条件变量那一章中有详细描述，请参见该章节。

\subsection*{首次尝试}
我们第一尝试用两个信号量来解决这个问题：empty和full，分别用来表示buffer空或满的状态。图31.5即put和get函数的代码，此次尝试解决生产者和消费者问题的代码见图31.6。

代码图31.5\\

代码图31.6\\

在本例中，生产者首先等待buffer为空以向其中写数据，类似的，消费者在取数据前等待buffer写满。首先，我们设想MAX为1（数组中仅有一个元素），来看看是否有效。

我们还是假设有两个线程，一个生产者一个消费者。我们在单CPU上验证一个特殊的场景。假设消费者先运行。因此，消费者会先执行上图中C1行的代码，调用sem\_wait(\&full)。因为full会先初始化为0，此次调用会将full减一（减为-1），阻塞消费者并等待另一个线程对full调用sem\_post()。

假设接着生产者运行。它会执行P1行，因此调用sem\_wait(\&empty)函数。不像消费者，由于empty的值被初始化为MAX（此例中是1），生产者执行此行后会继续执行。因此，empty会减1至0，然后生产者就会数据存入buffer的第一个位置（P2行）。生产者然后会继续执行P3行，调用sem\_post(\&full)，将full信号量的值由-1修改至0，并唤醒消费者（比如将其从阻塞队列移入就绪队列）。

在此例中，one of two事情可能会发生。如果生产者继续执行，它会循环又执行到P1行。这一次它会被阻塞，因为empty信号量的值是0。如果生产者被中断，然后消费者开始运行，它会调用sem\_wait(\&full)（C1行），并且发现buffer是满的再取出数据。另一种情况，正好是我们期望的行为。（待修改）

读者可以用更多的线程尝试这个例子（比如：多生产者多消费者）。应该仍然是有效的。

现在我们假设MAX的值大雨1（比如10）。此时，我们假设有多个生产者和多个消费者。会存在一个问题：竞争条件。读者发现会在哪里发生么？（花点时间找找看）如果你没看到，给点提示：仔细看put()和get()的代码。

好，让我们来看看这个问题。假设两个生产者（Pa和Pb）几乎同时调用了put()函数。假设生产者Pa首先得到运行，然后填充buffer第一个元素（f1行处fill=0）。在Pa获得将fill加1的机会前，它被中断了。生产者Pb开始运行，在行f1，它仍然将数据放到buffer的第零个元素，这意味着就得数据被覆写了！this is a no-no，这是禁忌; 我们不希望来自生产者的数据丢失。


\subsection*{解决方案：增加一个互斥量}
正如你看到的，我们忘记了这里是一个互斥现象。填充buffer和增加buffer的index是临界区，因此需要小心对付。那我们用二进制信号量并加一些锁来解决吧。图31.7即尝试的方法。

代码图31.7\\

现在，我们在整个put()和get()上下添加了一些锁，如NEW LINE注释所示。这貌似是正确的方法，但是它还是不能正常运行。为什么呢？死锁。为什么会发生死锁呢？花点时间考虑一下；试着找找看会在哪儿发生死锁。按照什么样的步骤执行才会使得程序死锁呢？


\subsection*{避免死锁}
现在你应该想出来了，答案是：设想有两个线程，一个生产者，一个消费者。消费者首先得到运行，它先获得mutex（行c0），然后对信号量full调用sem\_wait()；因为还没有数据，这个调用会引发消费者阻塞并因此让出CPU，重要的是消费者还占有着锁。

消费者接着运行。它有数据，如果能够运行的话，就可以唤醒消费者线程，那就万事大吉了。可是，他先是对二进制互斥信号量调用sem\_wait()（行p0）。锁已经被占有了，因此生产者也被卡住只能等待。

这就存在了一个简单的环。消费者持有了mutex并等待着某个线程给full信号。生产者可以给full信号，但是在等待这mutex。因此，生产者和消费者各自等待着对方：典型的死锁。

\subsection*{最后，可行方案}
为了解决这个问题，我们需要减少锁的作用域。图31.8即最终可行的解决方案。正如你看到的，我们简单地将mutex的获取和释放移到了恰好需要锁的临界区；full和empty等待和发信号代码放在的锁的外面。这是一个简单的可行的有界缓冲区，在多线程程序中常用的模型。understand it now，use it later。在多年后你会感谢我们的。至少，在期末考试是遇到相同的题目，你会感谢我们的。

代码图31.8\\

\section{读写锁}
读写锁

\section{哲学家就餐}

哲学家就餐问题

\section{如何实现信号量}

如何实现信号量s

\section{总结}

信号量章节总结












